package main.Q1_100;

import java.util.*;

public class Q41_50 {
    public static void main(String[] args) {
        System.out.println("Question41：缺失的第一个正数");
        System.out.println("Question42：接雨水");
        System.out.println("Question43：字符串相乘");
        System.out.println("Question44：");
        System.out.println("Question45：跳跃游戏Ⅱ");
        System.out.println("Question46：全排列");
        System.out.println("Question47：全排列Ⅱ");
        System.out.println("Question48：旋转图像");
        System.out.println("Question49：字母异位词分组");
        System.out.println("Question50：Pow(x,n)");
    }
}

class Question41 {
    //    public int firstMissingPositive(int[] nums) {
//        TreeSet<Integer> set=new TreeSet<>();
//        for (int num:nums) {
//            if (num>0) set.add(num);
//        }
//        int result=-1,pre=0;
//        for (int num:set) {
//            if (num-pre!=1) {
//                result=pre+1;
//                break;
//            }else pre=num;
//        }
//        if (result==-1) result=pre+1;
//        return result;
//    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

class Question42 {
    public int trap(int[] height) {
        int result = 0, length = height.length;
        int[] leftHeight = new int[length], rightHeight = new int[length];
        int temp = height[0];
        for (int i = 0; i < length; i++) {//i位置左侧最高值
            if (i == 0) leftHeight[i] = 0;
            else {
                if (temp > height[i]) leftHeight[i] = temp;
                else {
                    temp = height[i];
                    leftHeight[i] = 0;
                }
            }
        }
        temp = height[length - 1];
        for (int i = length - 1; i >= 0; i--) {//i位置右侧最高值
            if (i == length - 1) rightHeight[i] = 0;
            else {
                if (temp > height[i]) rightHeight[i] = temp;
                else {
                    temp = height[i];
                    rightHeight[i] = 0;
                }
            }
        }
        for (int i = 0; i < length; i++) {
            int min = Math.min(leftHeight[i], rightHeight[i]);
            if (min > height[i]) {//两侧高度大于当前高度，则能接雨水
                result += min - height[i];
            }
        }
        return result;
    }
}

class Question43 {
    public String multiply(String num1, String num2) {
        int length1 = num1.length(), length2 = num2.length(), index = 0;
        char[] str1 = num1.toCharArray(), str2 = num2.toCharArray();
        int[] ans = new int[length1 + length2];
        while (index < length1 + length2) {
            for (int i = 0; i < length1; i++) {
                for (int j = 0; j < length2; j++) {
                    if ((length1 - 1 - i) + (length2 - 1 - j) == index) ans[index] += (str1[i] - '0') * (str2[j] - '0');
                }
            }
            if (ans[index] > 9) {//进位
                ans[index + 1] += ans[index] / 10;
                ans[index] = ans[index] % 10;
            }
            index++;
        }
        StringBuffer result = new StringBuffer();
        boolean flag = true;
        for (int i = length1 + length2 - 1; i >= 0; i--) {
            if (flag && ans[i] == 0) continue;
            else {
                flag = false;
                result.append(ans[i]);
            }
        }
        if (result.length() == 0) return "0";
        return result.toString();
    }
}

class Question45 {
    //    public int jump(int[] nums) {
//        int length = nums.length;
//        int[] dp = new int[length];
//        for (int i = length - 1; i >= 0; i--) {
//            if (i == length - 1) {//最后一格
//                dp[i] = 0;
//                continue;
//            } else if (nums[i] == 0) {//当存在0步格子时，不能跳出
//                dp[i] = Integer.MAX_VALUE;
//                continue;
//            }
//            int min = Integer.MAX_VALUE;
//            for (int j = 1; j <= nums[i] && j + i < length; j++) {
//                min = Math.min(min, dp[i + j]);
//            }
//            if (min != Integer.MAX_VALUE) dp[i] = min + 1;//当前格子到最后一个的最少步数
//            else dp[i] = Integer.MAX_VALUE;
//        }
//        return dp[0];
//    }
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }
        return dp[nums.length - 1];
    }
}

class Question46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

class Question47 {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) continue;
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

class Question48 {
    public void process(int[][] matrix, int left, int right) {//宏观调度
        int leftUpRow = left, leftUpCol = left, rightUpRow = left, rightUpCol = right,//左上角，右上角
                leftDownRow = right, leftDownCol = left, rightDownRow = right, rightDownCol = right;//左下角，右下角
        for (int i = 0; i < right - left; i++) {
            int temp1 = matrix[leftUpRow][leftUpCol], temp2 = matrix[rightUpRow][rightUpCol],
                    temp3 = matrix[leftDownRow][leftDownCol], temp4 = matrix[rightDownRow][rightDownCol];
            matrix[leftUpRow][leftUpCol] = temp3;
            matrix[rightUpRow][rightUpCol] = temp1;
            matrix[leftDownRow][leftDownCol] = temp4;
            matrix[rightDownRow][rightDownCol] = temp2;
            leftUpCol++;
            rightUpRow++;
            rightDownCol--;
            leftDownRow--;
        }
    }

    public void rotate(int[][] matrix) {
        int right = matrix.length - 1, left = 0;
        for (int i = 0; i < matrix.length / 2; i++) {
            process(matrix, left, right);
            left++;
            right--;
        }
    }
}

class Question49 {
//    public String process(String s){
//        char[] str=s.toCharArray();
//        Arrays.sort(str);
//        StringBuffer sortStr=new StringBuffer();
//        for (char c:str) sortStr.append(c);
//        return sortStr.toString();
//    }
//    public List<List<String>> groupAnagrams(String[] strs) {
//        List<List<String>> list=new ArrayList<>();
//        String[] processStr=new String[strs.length];
//        for (int i=0;i< strs.length;i++){
//            processStr[i]=process(strs[i]);
//        }
//        Set<String> set=new HashSet<>();
//        for (int i=0;i<strs.length;i++){
//            if (set.contains(processStr[i])) continue;
//            else {
//                set.add(processStr[i]);
//                List<String> tempList=new ArrayList<>();
//                for (int j=i;j< strs.length;j++){
//                    if (processStr[i].equals(processStr[j])){
//                        tempList.add(strs[j]);
//                    }
//                }
//                list.add(tempList);
//            }
//        }
//        return list;
//    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String temp = new String(arr);
            if (map.containsKey(temp)) {
                map.get(temp).add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(temp, list);
            }
        }
        for (String key : map.keySet()) {
            result.add(map.get(key));
        }
        return result;
    }
}

class Question50 {
    public double myPow(double x, int n) {
        if (x == 0.0f) return 0.0d;
        long b = n;
        double res = 1.0;
        if (b < 0) {
            x = 1 / x;
            b = -b;
        }
        while (b > 0) {
            if ((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}